Incremental search reuses information from previous searches to find solutions to a series of similar search problems potentially faster than is possible by solving each search problem from scratch. This is important because many AI systems have to adapt their plans continuously to changes in (their knowledge of) the world. AI has developed several ways of speeding up searches by trading off the search time and the cost of the resulting path, which includes using inadmissible heuristics (Pohl 1973, 1970) and search with limited look ahead (Korf 1990; Ishida and Korf 1991; Koenig 2001), which is also called real-time or agent-centered search. In this article, we discuss a different way of speeding up searches, namely, incremental search. Incremental search is a search technique for continual planning (or, synonymously, replanning, plan reuse, and lifelong planning) that reuses information from previous searches to find solutions to a series of similar search problems potentially faster than is possible by solving each search problem from scratch.

Moving Target Search (MTS) is a dynamic path planning problem, where an agent is trying to reach a moving entity with a minimum path cost. Problems of this nature can be found in video games and dynamic robotics, which require fast processing time (real time). In this work, we introduce a new algorithm for this problem - the Moving Target Search with Subgoal Graphs (MTSub). MTSub is based on environment abstraction and uses Subgoal Graphs to speed up the searches for a minimal cost route to the target. The algorithm is optimal with respect to the knowledge that the agent has during the search. Experimental results show that MTSub can be used in real-time applications (e.g., applications requiring 5 microseconds response time per step). The experiments compared MTSub to G-FRA*, which is the best known dynamic algorithm so far, showing that MTSub is up to 29 times faster in average time per step, and up to 186 times faster in maximum time per step.

Incremental search reuses information from previous searches to find solutions to a series of similar search problems potentially faster than is possible by solving each search problem from scratch. This is important because many AI systems have to adapt their plans continuously to changes in (their knowledge of) the world. In this article, we give an overview of incremental search, focusing on LIFELONG PLANNING A*, and outline some of its possible applications in AI.